package de.flojo.game;

import java.util.ArrayList;
import java.util.List;

public class RamerDouglasPeucker
{
	static ArrayList<Point> compute( List<Point> input, double epsilon ) {

		ArrayList<Point> result = new ArrayList<Point>();

		double dmax = 0;
		int index = 0;
		int end = input.size();

		Point p1 = input.get(0);
		Point p2 = input.get(end-1);

		for (int i = 1; i < end-2; i++) {
			double d = distToLine( input.get(i), p1, p2 );
			if (d > dmax) { dmax = d; index = i; }
		}

		if (dmax > epsilon) {
			ArrayList<Point> res1 = compute( input.subList(0,index), epsilon );
			ArrayList<Point> res2 = compute( input.subList(index,end-1), epsilon );
			result.addAll(res1);
			result.addAll(1,res2);
		} else {
			result.add(p1);
			result.add(p2);
		}

		return result;
	}
	
	static double k_cosine(Point p1, Point p2, Point p3)
	{
		double x1 = p2.x-p1.x;
		double y1 = p2.y-p1.y;
		double x2 = p2.x-p3.x;
		double y2 = p2.y-p3.y;

		double l1 = Math.sqrt(x1*x1 + y1*y1);
		double l2 = Math.sqrt(x2*x2 + y2*y2);
		return (x1*x2+y1*y2) / (l1*l2);
	}

	static double distToLine( Point p, Point l1, Point l2 )
	{
		double nx = l2.x - l1.x;
		double ny = l2.y - l1.y;
		double len = Math.sqrt(nx*nx+ny*ny);
		nx = nx/len; ny = ny/len;

		// t - ( t*n ) * n
		double tx = l1.x - p.x;
		double ty = l1.y - p.y;

		double f = tx*nx + ty*ny;
		nx = f*nx; ny = f*ny;
		tx = tx - nx;
		ty = ty - ny;

		return Math.sqrt(tx*tx+ty*ty);
	}
	
	
}
